//You are given two integer arrays nums1 and nums2 sorted in ascending order and
// an integer k. 
//
// Define a pair (u, v) which consists of one element from the first array and o
//ne element from the second array. 
//
// Return the k pairs (u1, v1), (u2, v2), ..., (uk, vk) with the smallest sums. 
//
//
// 
// Example 1: 
//
// 
//Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
//Output: [[1,2],[1,4],[1,6]]
//Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,
//6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
// 
//
// Example 2: 
//
// 
//Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
//Output: [[1,1],[1,1]]
//Explanation: The first 2 pairs are returned from the sequence: [1,1],[1,1],[1,
//2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
// 
//
// Example 3: 
//
// 
//Input: nums1 = [1,2], nums2 = [3], k = 3
//Output: [[1,3],[2,3]]
//Explanation: All possible pairs are returned from the sequence: [1,3],[2,3]
// 
//
// 
// Constraints: 
//
// 
// 1 <= nums1.length, nums2.length <= 104 
// -109 <= nums1[i], nums2[i] <= 109 
// nums1 and nums2 both are sorted in ascending order. 
// 1 <= k <= 1000 
// 
// Related Topics 堆 
// 👍 184 👎 0


package leetcode.editor.cn;

import java.util.*;

//Java：Find K Pairs with Smallest Sums
class P373FindKPairsWithSmallestSums {
    public static void main(String[] args) {
        Solution solution = new P373FindKPairsWithSmallestSums().new Solution();
        // TO TEST
        solution.kSmallestPairs(new int[]{1, 1, 2
        }, new int[]{1, 2, 3}, 2);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> kSmallestPairs1(int[] nums1, int[] nums2, int k) {
            List<List<Integer>> result = new ArrayList<>();
            Comparator<List<Integer>> comparator = (a, b) -> -(a.get(0) + a.get(1)) + (b.get(0) + b.get(1));
            PriorityQueue<List<Integer>> heap = new PriorityQueue<>(comparator);
            for (int i = 0; i < nums1.length; i++) {
                for (int j = 0; j < nums2.length; j++) {
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(nums1[i]);
                    list.add(nums2[j]);
                    if (heap.size() < k) {
                        heap.add(list);
                    } else {
                        List<Integer> peek = heap.peek();
                        if (comparator.compare(list, peek) > 0) {
                            heap.poll();
                            heap.add(list);
                        } else {
                            break;
                        }
                    }
                }
            }
            while (heap.size() > 0) {
                result.add(heap.poll());
            }
            return result;
        }

        public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            List<List<Integer>> res = new ArrayList<>();
            int n = nums1.length, m = nums2.length;
            if (n == 0 || m == 0) {
                return res;
            }
            // 利用一个数组来保存nums1中每个元素对应的最小组合的nums2下标，初始值为0，因为刚开始每个元素对应的最小组合肯定是对面的第一个元素
            int[] f = new int[n];

            // 外层最多遍历k次，获取前k个最小值
            while (res.size() < k) {
                int cur = 0;
                // 遍历每个nums1元素对应nums2最小可用组合，并获取最小组合
                for (int i = 1; i < n; i++) {
                    // 当前i位置可用组合已经用完了
                    if (f[i] == m) {
                        continue;
                    }
                    // 比较获取最小的组合
                    if (f[cur] == m || nums1[cur] + nums2[f[cur]] > nums1[i] + nums2[f[i]]) {
                        cur = i;
                    }
                }
                // 所有的组合都用完了，就跳出循环
                if (f[cur] == m) {
                    break;
                }
                // 答案中添加当前组合
                res.add(Arrays.asList(nums1[cur], nums2[f[cur]]));
                // 当前组合中nums1元素对应的nums2元素下标加一，这样就不会重复用到之前的组合
                f[cur]++;
            }

            return res;

        }


    }
//leetcode submit region end(Prohibit modification and deletion)

}